/**
 * Created by L.jp
 * Description:给定一个排序数组和一个目标值，在数组中找到目标值，
 * 并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * User: 86189
 * Date: 2022-02-25
 * Time: 19:53
 */
/*  思路：还是利用二分查找算法，不断缩小范围查找目标值，找到就返回下标，找不到就返回要插入的位置‘
         遍历完数组后，没有找到这个数就是要插入到两个指针相遇的位置
*
* */
public class Solution {
    public static int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid;
            }else{
                return mid;
            }
        }
        return left;

    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 7, 8, 9, 10, 11, 12, 13, 14};
        int target=5;
        System.out.println(searchInsert(nums, target));
    }

}
